LRU Cache
Leetcode #146 | Medium | Связный список | Хэш-таблицы | Design
Идея
HashMap {ключ: Node} и двусвязный список из Node (next, prev, key, val)
Для удобства фиктивный head и tail. Обращение - удаляем из места и ставим в конец. Если капасити превышено удаляем head.next
Big-O
- Время
O(1) - Память
O(N)
Код
class LRUCache {
class Node {
int key, val;
Node prev, next;
Node(int k, int v) { key = k; val = v; }
}
private int cap;
private Map<Integer, Node> map = new HashMap<>();
private Node head = new Node(0, 0), tail = new Node(0, 0);
public LRUCache(int capacity) {
cap = capacity;
head.next = tail; tail.prev = head;
}
public int get(int key) {
if (!map.containsKey(key)) return -1;
Node node = map.get(key);
remove(node); insert(node);
return node.val;
}
public void put(int key, int value) {
if (map.containsKey(key)) remove(map.get(key));
Node node = new Node(key, value);
insert(node); map.put(key, node);
if (map.size() > cap) {
Node lru = head.next;
remove(lru); map.remove(lru.key);
}
}
private void remove(Node node) { node.prev.next = node.next; node.next.prev = node.prev; }
private void insert(Node node) {
Node prev = tail.prev;
prev.next = node; node.prev = prev;
node.next = tail; tail.prev = node;
}
}